1. Field of the Invention
The present invention relates to the field of solving real-world constraint problems and, more particularly, to a method and system for optimizing constraint models.
2. Description of the Related Art
Cyclic matrices are frequently encountered in optimization problems, such as network problems, the traveling salesman problem, labor scheduling problems, and certain reliability problems. An nth-order matrix A, with elements a(j, k)≡a(k-j) that depend on only k-j, and that are periodic so that a(k+n)=a(k), is called cyclic. Equivalence among several necessary conditions is required for a square complex matrix to be cyclic. The cyclic property of the constraint matrix can be exploited in order to develop efficient solutions of optimization problems. For example, the cyclic property of the constraint matrix can be utilized to devise models and efficient solution procedures for cyclic optimization problems.
A 0-1 vector is said to be circular if its l's occur consecutively, where the first and last entries are considered to be consecutive. A matrix is called column (row) circular if its columns (rows) are circular.
Cyclic sequences and permutations are important problems in combinatorial theory. An example of a cyclic combinatorial problem is the necklace problem is as follows: how many distinct necklace patterns are possible with n beads, which are available in r different colors? The present invention addresses a simpler problem: how many distinct necklace patterns are possible with n beads, m of which are black, and the rest are white? If mirror image necklaces are considered equivalent, the question becomes: what is the number of bracelets (reversible necklaces) that can be formed with n black and white beads, m of which are black? Both the necklace and the bracelet problems are directly applicable to optimization problems with cyclic 0-1 matrices. The two colors of the beads correspond to O's and 1's in a cyclic 0-1 constraint coefficient matrix.
Because Integer Linear Programming (ILP) problems are known to be difficult to solve (NP hard) and have numerous applications in many areas of optimization, such as cyclic scheduling and network problems, it would be desirable to provide a method that is generally applicable to all integer linear programming (ILP) problems of the form: minimize 1Tx, subject to Ax≧r, where x≧0 and integer, and A is a cyclic 0-1 matrix.
Thus, a cyclic combinatorial method and system solving the aforementioned problems is desired.